//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 
//
// 返回被除数 dividend 除以除数 divisor 得到的商。 
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
//
// 
//
// 示例 1: 
//
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 
//
// 示例 2: 
//
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2 
//
// 
//
// 提示： 
//
// 
// 被除数和除数均为 32 位有符号整数。 
// 除数不为 0。 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。 
// 
// Related Topics 位运算 数学 
// 👍 773 👎 0

package leetcode.editor.cn;

import java.util.Map;

/**
 * [29]两数相除
 */
public class DivideTwoIntegers {
    public static void main(String[] args) {
        Solution solution = new DivideTwoIntegers().new Solution();
        int result;
//        result = solution.divide(10,3);
//        if (result != 3) {
//            System.out.println("--1--");
//        }
//
//        result = solution.divide(7,-3);
//        if (result != -2) {
//            System.out.println("--2--");
//        }

//        result = solution.divide(0,1);
//        if (result != 0) {
//            System.out.println("--3--");
//        }

        result = solution.divide(-2147483648, -1);
        if (result != 0) {
            System.out.println("--3--");
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        boolean negative = (dividend ^ divisor) < 0;

        long t = Math.abs((long) dividend);
        long d = Math.abs((long) divisor);
        int result = 0;
        for (int i = 32; i >= 0 ; i--) {
            if ((t>>i) >= d) {
                t -= (d<<i);
                result += 1<<i;

            }
        }
        return negative?-result:result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}